package com.algorithm.floyd;

import java.util.Arrays;

public class Graph {
    char[] vertexs;
    int[][] dis;
    // 保存到达目标顶点的前驱结点
    int[][] pre;

    public Graph(int length,int[][] maxtrix,char[] vertexs){
       this.vertexs = vertexs;
       this.dis = maxtrix;
       this.pre = new int[length][length];
       //对pre数组进行初始化,存放前驱结点的下标
        for(int i = 0;i<length;i++){
            Arrays.fill(pre[i],i);
        }
    }


    public void showGrap(){
        System.out.println("距离矩阵为：");
        for(int[] arr1 : dis){
            for (int arr : arr1){
                System.out.format("%-6d",arr);
            }
            System.out.println();
        }
        System.out.println("前驱矩阵为");
        for(int[] arr1 : pre){
            for (int arr : arr1){
                System.out.format("%-6d",arr);
            }
            System.out.println();
        }
    }


    public void floyd(){
        int len = 0;
        //对中间结点进行遍历
        for(int k=0;k<vertexs.length;k++){
            //对矩阵行遍历
            for(int i = 0;i<vertexs.length;i++){
                //对矩阵列遍历
                for(int j = 0;j<vertexs.length;j++){
                    len = dis[i][k] + dis[k][j];
                    if(len < dis[i][j]){
                        dis[i][j] = len;
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }
    }
}
